/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    pair<ListNode*,ListNode*> reverse(ListNode* head){

        ListNode* pre=nullptr;
        ListNode* cur=head;
        while(cur){
            ListNode* next=cur->next;
            cur->next=pre;
            pre=cur;
            cur=next;
        }

        return {pre,head};
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        
        ListNode dummy;
        dummy.next=head;
        ListNode* pre=&dummy;
        while(head){
            ListNode* tail=pre;
            for(int i=0;i<k;++i){
                tail=tail->next;
                if(tail==nullptr){
                    return dummy.next;
                }
            }
            ListNode* tailNext=tail->next;
            tail->next=nullptr;
            auto ret=reverse(head);

            pre->next=ret.first;
            ret.second->next=tailNext;
            pre=ret.second;
            head=tailNext;
        }

        return dummy.next;
    }
};
